This application relates generally to disc drive caching techniques and more particularly to a buffer management system for controlling the transfer of data between a host computer and a disc of a disc drive.
In a disc drive, data is stored on one or more discs coated with a magnetizable medium. Data is written to the discs by an array of transducers, typically referred to as read/write heads, mounted to a radial actuator for movement of the heads relative to the discs. The information is stored on a plurality of concentric circular tracks on the discs until such time that the data is read from the discs by the read/write heads. Each of the concentric tracks is generally divided into a plurality of separately addressable data sectors. The heads are used to transfer data between a desired track and an external environment, which includes, among many components, a host computer. During a read operation the head senses the data previously written on the disc track and transfers the information to the external environment. During a write operation, data is written onto the disc track. Once the data is written to the disc, each sector holds a block of data, which is the absolute smallest quantity that can be written to the disc during a single write operation. Adjacent blocks, commonly referred to as chunks, or clusters, are typically written to the disc during a single write operation referred to as a command. Critical to both of these operationsxe2x80x94reading and writingxe2x80x94is the accurate locating of the head over the center of the desired track.
Typically, the heads are positioned with respect to the disc surfaces by an actuator voice coil motor. The voice coil motor is responsible for pivoting the actuator body about a pivot shaft, thus moving the heads across the disc surfaces. The actuator thus allows the heads to move back and forth in an accurate fashion between an inner radius and an outer radius of a disc. The actuator arm is driven by a control signal fed to the voice coil motor at the rear end of the actuator arm. A servo control system is used to sense the position of the actuator and control the movement of the head above the disc using servo signals read from a disc surface in the disc drive. The servo control system relies on servo information stored on the disc. The signals from this information generally indicate the present position of the head with respect to the disc, i.e., the current track position. The servo control system uses the sensed information to maintain head position or determine how to optimally move the head to a new position centered above a desired track. The servo control system then delivers a control signal to the voice control motor to position the head over a desired new track or to maintain the position over the desired current track.
The transfer of files between the host computer and the disc is controlled in a multi-level setting characterized by a bi-level transfer scheme. At a macroscopic level, track sectors are selected to contain the data sectors of which the file is divided. More specifically, and in a microscopic sense, cells along a track are magnetized to correspond to the bit structure of the file for the purposes of subsequent reading. A disc drive typically includes a buffer to implement this bi-level transfer scheme. The purpose of the buffer is to accept the sectors of data during its transfer between the host computer and the disc and then transfer the data to the proper componentxe2x80x94either the host computer or the disc.
Typically, the system microprocessor contains programming designed to locate the sectors on the track where the data is to be read from or written to. The microprocessor is also programmed to control the transfer of the file at the sector, or macroscopic, level. The transfer of data to and from the buffer is accomplished in character-by-character fashion. The conventional method of accomplishing a transfer in a character-by-character environment is through the use of state machines, such as a buffer controller, a host interface controller, and a disc interface controller.
As described in U.S. Pat. No. 5,276,662, the transfer of files between the host and the discs is carried out under the overall control of the system microprocessor and a more precise control of the state machine controllers. For example, when a file is to be written to a disc, the host computer prompts the system microprocessor with generalized information which allows the microprocessor to define the sectors on the track to which the file is to be written. The microprocessor then initiates the transfer by implementing operations which result in transfer at the sector level. Such operations include commanding the servo control system to position the head over the selected track which is to receive the file and identifying a segment of the buffer which is to be used in the transfer. The microprocessor commands the host interface controller to initiate the transfer of the data to the buffer segment. Conventionally, the host interface controller, working in conjunction with the buffer controller and the host computer, provides precise control over the buffer in the transfer of characters of the file into sector blocks of the buffer segment. The disc interface controller controls the transfer of the blocks of data from the buffer segment to the appropriate sectors on a disc pursuant to commands issued by the system microprocessor once the read/write heads are positioned over the track that is to receive the file. A read/write circuit connected to the read/write heads then magnetizes the cells along the data tracks.
Conventionally, counters and interrupts are used in conjunction with the buffers to xe2x80x9cwatch overxe2x80x9d the transfer of data to the buffer. The counters, which are typically located within the host and disc interface controllers, count the number of transfers that occur between both the host and the buffer and the disc and the buffer. Based upon this calculation, an interrupt generator supplies an interrupt to the microprocessor immediately after a selected number of transfers to the buffer have occurred. The use of counters and interrupts is to inquire as to whether the buffer is full when a transfer is to take place.
The most significant drawback of disc drives is a relatively long delay between the time that a read or write operation is initiated and the time that it is mechanically completed. This delay includes a seek latency, the time during which the read/write heads are moved to a desired track, a rotational latency, the time during which the disc rotates until a desired track sector is under the read/write head, and an additional delay corresponding to the time during which data blocks are read from or written onto the disc surface. Due to the aforementioned delays, the speed with which a disc drive operates is typically slower than that of the other components of the computer system. That being the case, it is advantageous, for total system performance, for the host system to transfer the data it wishes to write to a buffer, then allow the drive to commit that data to a disc at a later time that is optimal for the drive to perform the (mechanical) task of putting the data on the media. This concept, usually called write caching, is common to data storage devices.
A well-known means for reducing the number of disc accesses associated with almost any software application involves the use of a single common cache memory. The cache memory, typically a volatile random access memory (VRAM) device, stores blocks of data that are read from, or blocks that are to be written onto, the disc. Once the system issues a disc read operation the cache is first checked to see if the requested data block is already available, thus avoiding the typical physical disc read. If the data block is not available, then the system instructs the read/write heads to perform a disc read, from which the data is transferred to the cache.
As described in U.S. Pat. No. 5,765,193, it is common for requests of data from a disc to be specific as to related data, such as data files. The data files will be written to and stored on the disc in adjacent sectors of the track. Accordingly, a principle of reference is commonly known among computer programmers illustrating xe2x80x9cwhen data is stored or to be stored at one location, it is highly probable that data stored or to be stored at physically adjacent locations will be accessed either simultaneously or soon thereafter each other.xe2x80x9d To realize this principle, data, which is to be written to a disc, is commonly transferred to a write cache prior to recording on the disc. This procedure is advantageous in two respects. First, it allows the host to quickly access the data without having to perform an actual read operation on the disc. In order to read directly from the write cache, the system must keep track of which data blocks are being held in the cache instead of the disc. Second, it gives the read/write heads time to catch up with the other components of the computer.
Once the cache is filled, the system microprocessor initiates write operations to transfer the data blocks in the cache to the disc drive. As further described in U.S. Pat. No. 5,765,193, there are several methods for managing the xe2x80x9corderlyxe2x80x9d transfer of data from the write cache to the disc. One common technique for managing the write cache is to supplement the disc write operation with instructions to search the write cache for adjacent data blocks. The existence of at least two adjacent data blocks defines a cluster, which the system will transfer in whole pursuant to the disc write operation. By reducing the number of disc accesses, this technique decreases the overall number of time-consuming seek operations. A second known technique involves keeping a xe2x80x9cleast recently usedxe2x80x9d (LRU) queue, which comprises a list of data blocks in its order of use. This technique uses a virtual block number, a number assigned to the data block in relation to its intended storage location on the disc, to rank the data blocks in relation to the order of most recent use by the system. Based on a theory that data blocks more recently used are more likely to be used again prior to less recently used data blocks, the system transfers the latter to the disc while retaining the former in the write cache for quick access by the central processing unit. A third, and more outdated, technique is to simply remove blocks from the cache on a first-in-first-out basis.
While all three techniques relating to the transfer of data from the buffer to the disc provide an effective means of implementing the storage and retrieval of data files, problems have arisen in conjunction with data transfer to a disc from buffers of limited data space. Particularly, if the data from the buffer is not transferred to the disc in first-in-first-out fashion, then the buffer sectors from which the data was transferred cannot be reused until the buffer sectors lower in order from the emptied sectors were, in fact, emptied. For example, in a 100-sector buffer, if sectors 45 through 50 were written to the disc, then that particular buffer space cannot be re-used by the host until buffer sectors 1 through 44 have been emptied. When dealing with disc drives of limited amounts of buffer data space, this xe2x80x9csequentialxe2x80x9d buffer accessing method is a significant disadvantage to the host computer with respect to write caching.
Against this backdrop the present invention has been developed. The present invention is a means for rearranging buffer sectors so that buffer data space can be used more efficiently. In particular, the vectored buffer management system, in accordance with the present invention, hereinafter called xe2x80x9cVBM,xe2x80x9d provides a means for rearranging the buffer space so that transfer of data into and out of the buffer can be done in an arbitrary or random fashion. In essence, VBM allows data to be written to and from the buffer sectors in a non-sequential fashion. VBM contains three components: an algorithmic component, a hardware component, and a software component.
The algorithmetic component defines a model, referred to as the VBM table, of the data buffer as a logically organized singly linked list of sectors. Each entry in the VBM table represents a single sector of the buffer. Each sector of the buffer stores a data block having a logical block address (LBA) representing a sector on a disc in the disc drive. The buffer sector where the hardware component is currently positioned is referred to as the index sector. The value of each index sector is xe2x80x9cnextxe2x80x9d sector, a physical buffer sector number denoting the xe2x80x9cnextxe2x80x9d sector for the hardware component to reference upon conclusion of the transfer of data to or from the current index sector.
The hardware component is responsible for the physical transfer of data into and out of the buffer. During a disk write operation, the hardware component uses the xe2x80x9cVBMxe2x80x9d table as the basis for the management of the data transfer. This is accomplished by setting a host address pointer (HAP), which is responsible for committing the data to the buffer, and the disc address pointer (DAP), which is responsible for transferring the data from the buffer to the disc. The initial value of these pointers is arbitrarily selected by the software component. The HAP and the DAP both are coupled to a host next pointer (HNP) and a disc next pointer (DNP), respectively. The functions of the next pointers are to read the next sector value from the index sector in order to direct the address pointers to the next sector. The hardware also provides an automated traversal function independent of the task that is managing the buffer allocation such that the function can still traverse a large number of table entries, even when the CPU is performing another task.
The software component maximizes the advantage of write caching by ensuring that the maximum possible number of buffer sectors are available to new host write commands at any given time, and by minimizing the number of disk operations needed to complete the requests from the host. More particularly, the software provides the mechanism for creating and maintaining the VBM table that is used by hardware to direct data transfers into and out of the data buffer. The software component is further responsible for administering control of the hardware component. By creating a list of free buffer sectors, the software component also provides for the ability of VBM to separate cached data from free space, merge buffer segments of the buffer table into single disc operations when beneficial, reuse any buffer sectors that hold redundant data, and return buffer sectors to the free list in any order.
These and various other features, as well as advantages which characterize the present invention, will be apparent from a reading of the following detailed description and a review of the associated drawings.